package com.gitee.feizns.explore.data_structure.graph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;

/**
 * @author feizns
 * @since 2020/2/28
 */
public class FindMinHeightTrees {

    public static void main(String[] args) {
        System.out.println(findMinHeightTrees(4, new int[][]{{1, 0}, {1, 2}, {1, 3}}));
    }

    public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
        G g = create(edges, n);
        int x = n;
        List<Integer> leafs = g.leafs();
        while ( !leafs.isEmpty() && x > leafs.size() ) {
            x -= leafs.size();
            for (Integer l : leafs)
                g.removeEdge(l);
            leafs = g.leafs();
        }
        return g.nodes.stream().collect(Collectors.toList());
    }

    private static G create(int[][] edges, int size) {
        G g = new G(size);
        for (int i = 0; i < edges.length; i++)
            g.addEdge(edges[i][0], edges[i][1]);
        return g;
    }

    private static class G {
        private Set<Integer>[] g;
        Set<Integer> nodes = new HashSet<>();
        private int[] in;
        public G(int size) {
            this.g = new TreeSet[size];
            for (int i = 0; i < g.length; i++)
                g[i] = new TreeSet<>();
            this.in = new int[size];
            for (int i = 0; i < size; i++)
                nodes.add(i);
        }
        public Set<Integer> adj(int v) { return g[v]; }
        public void addEdge(int s, int t) {
            g[s].add(t);
            g[t].add(s);
            in[s]++;
            in[t]++;
        }
        public void removeEdge(int s) {
            nodes.remove(s);
            Set<Integer> a = g[s];
            for (Integer e : a) {
                g[s].remove(e);
                g[e].remove(s);
                in[e]--;
            }
            in[s]--;
        }
        public List<Integer> leafs() {
            List<Integer> ret = new LinkedList<>();
            for (int i = 0; i < g.length; i++) {
                if ( in[i] == 1 )
                    ret.add(i);
            }
            return ret;
        }
    }

}
